Corelab Seminar
2019-2020
Fotis Iliopoulos
Girth-reducibility and the algorithmic barrier for coloring
Abstract.
All known efficient algorithms for constraint satisfaction problems are stymied by random instances. For example, no efficient algorithm is known that can q-color a random graph with average degree (1 + ε)q ln q, even though random graphs remain q-colorable for average degree up to (2 − o(1))q ln q. Similar failure to find solutions at relatively low constraint densities is known for random CSPs such as random k-SAT and other hypergraph-based problems. The constraint density where algorithms break down for each CSP is known as the “algorithmic barrier” and provably corresponds to a phase transition in the geometry of the space of solutions [Achlioptas and Coja-Oghlan 2008]. In this talk, I will discuss my recent paper which aims to shed light on the following question: Can algorithmic success up to the barrier for each CSP be ascribed to some simple deterministic property of the inputs? In particular, I will focus on the problem of coloring graphs and hypergraphs.